package ljl.codetop300;

import java.util.List;

public class _120_min_total {

  /**
   * 居然搞出来了，虽然很吃力
   */
  static class test {
    public int minimumTotal(List<List<Integer>> triangle) {
      int[] dp = new int[triangle.get(triangle.size() - 1).size()];
      dp[0] = triangle.get(0).get(0);
      for (int i = 1; i < triangle.size(); i++) {
        for (int j = i; j >= 0; j--) {
          if (j < i) {
            int min = dp[j];
            if (j > 0) {
              min = Math.min(min, dp[j - 1]);
            }
            dp[j] = min + triangle.get(i).get(j);
          } else {
            dp[j] = triangle.get(i).get(j) + dp[j - 1];
          }
        }
      }
      int min = Integer.MAX_VALUE;
      for (int i : dp) {
        min = Math.min(min, i);
      }
      return min;
    }
  }

  /**
   * 确实比我的清晰，没白看
   * 看来自己写完必须看别人的解法，不然就完犊子蛋包子了
   */
  static class off_dp1 {
    public int minimumTotal(List<List<Integer>> triangle) {
      int n = triangle.size();
      int[][] f = new int[n][n];
      f[0][0] = triangle.get(0).get(0);
      for (int i = 1; i < n; ++i) {
        f[i][0] = f[i - 1][0] + triangle.get(i).get(0);
        for (int j = 1; j < i; ++j) {
          f[i][j] = Math.min(f[i - 1][j - 1], f[i - 1][j]) + triangle.get(i).get(j);
        }
        f[i][i] = f[i - 1][i - 1] + triangle.get(i).get(i);
      }
      int minTotal = f[n - 1][0];
      for (int i = 1; i < n; ++i) {
        minTotal = Math.min(minTotal, f[n - 1][i]);
      }
      return minTotal;
    }
  }

  static class off_dp2 {
    public int minimumTotal(List<List<Integer>> triangle) {
      int n = triangle.size();
      int[] f = new int[n];
      f[0] = triangle.get(0).get(0);
      for (int i = 1; i < n; ++i) {
        f[i] = f[i - 1] + triangle.get(i).get(i);
        for (int j = i - 1; j > 0; --j) {
          f[j] = Math.min(f[j - 1], f[j]) + triangle.get(i).get(j);
        }
        f[0] += triangle.get(i).get(0);
      }
      int minTotal = f[0];
      for (int i = 1; i < n; ++i) {
        minTotal = Math.min(minTotal, f[i]);
      }
      return minTotal;
    }
  }

  static class copy_dp2 {
    public int minimumTotal(List<List<Integer>> triangle) {
      int n = triangle.size();
      int[] f = new int[n];
      f[0] = triangle.get(0).get(0);
      for (int i = 1; i < n; i++) {
        f[i] = f[i - 1] + triangle.get(i).get(i);
        for (int j = i - 1; j > 0; j--) {
          f[j] = Math.min(f[j - 1], f[j]) + triangle.get(i).get(j);
        }
        f[0] += triangle.get(i).get(0);
      }
      int res = Integer.MAX_VALUE;
      for (int num : f) {
        res = Math.min(num, res);
      }
      return res;
    }
  }
}
